/* TwentyFour.java
 * Author: liuex
 * 2007-12-18 ����04:06:47
 *
 * Note: 
 */
package org.lex.tf.core;

import java.util.*;

public class TwentyFour2
{
	/**
	 * �ҳ������ܼ����24�ı��ʽ<br>
	 * bugs:<br>
	 * ������ظ��ı��ʽ
	 */
	public TwentyFour2()
	{}

	public static void main( String[] args )
	{
		TwentyFour2 tf = new TwentyFour2();
		System.out.println( tf.find( 4, 3, 7, 9 ) );
		System.out.println( tf.find( 1, 1, 2, 9 ) );
		System.out.println( tf.find( 5, 5, 3, 3 ) );
	}

	public Collection<String> find( int a, int b, int c, int d )
	{
		int[] src = new int[]{ a, b, c, d };
		Collection<Expression> e = this.find( 24, src );
		ArrayList<String> finds = new ArrayList<String>( e.size() );
		for( Iterator<Expression> iter = e.iterator(); iter.hasNext(); )
			finds.add( iter.next().toString() );
		return finds;
	}

	private Collection<Expression> find( final int expect, final int[] src )
	{
		ArrayList<Expression> finds = new ArrayList<Expression>();
		addUnique( this.find22( expect, src ), finds );
		addUnique( this.find13( expect, src ), finds );
		return finds;
	}

	private static <T> Collection<T> addUnique( Collection<T> src, Collection<T> dest )
	{
		int size = 0;
		if( null != src )
			size = src.size();
		if( null == dest )
			dest = new ArrayList<T>( size );
		if( null == src )
			return dest;
		for( T e : src )
			if( false == dest.contains( e ) )
				dest.add( e );
		return dest;
	}

	private static final int[][] C42 = org.lex.math.pc.Combination.combinations( 4, 2 );

	private Collection<Expression> find22( int expect, int[] src )
	{
		ArrayList<Expression> finds = new ArrayList<Expression>();
		for( int i = 0; i < C42.length; i++ )
		{
			int[] indexes = C42[i];
			int a = src[indexes[0]];
			int b = src[indexes[1]];
			int[] subSrc = org.lex.utils.Arrays.removeIndexes( src, indexes );
			int c = subSrc[0];
			int d = subSrc[1];
			List<Expression> first = this.allPossibleProducts( a, b );
			List<Expression> second = this.allPossibleProducts( c, d );
			for( Expression fe : first )
				for( Expression se : second )
					for( Expression e : this.allPossibleProducts( fe, se ) )
						if( expect == e.getValue() )
							finds.add( e );
		}
		return finds;
	}

	private Collection<Expression> find13( int expect, int[] src )
	{
		if( 0 == src.length )
			return Collections.emptyList();
		else if( 1 == src.length )
		{
			if( expect == src[0] )
				return wrap( new Expression( src[0] ) );
			else
				return Collections.emptyList();
		}
		else
		{
			ArrayList<Expression> finds = new ArrayList<Expression>();
			// more than one number
			for( int i = 0; i < src.length; i++ )
			{
				int got = src[i];
				int[] subSrc = this.newArray( src, i );
				// got+value=expect
				int value = 0;
				Iterator<Expression> iter = null;
				if( got <= expect )
				{
					value = expect - got;
					iter = this.find13( value, subSrc ).iterator();
					while( iter.hasNext() )
						finds.add( iter.next().add( got ) );
				}
				// got-value=expect
				if( got >= expect )
				{
					value = got - expect;
					iter = this.find13( value, subSrc ).iterator();
					while( iter.hasNext() )
						finds.add( new Expression( got ).minus( iter.next() ) );
				}
				// value-got=expect
				value = expect + got;
				iter = this.find13( value, subSrc ).iterator();
				while( iter.hasNext() )
					finds.add( iter.next().minus( got ) );
				// value*got=expect
				if( expect >= got && 0 != got && (expect % got == 0) )
				{
					value = expect / got;
					iter = this.find13( value, subSrc ).iterator();
					while( iter.hasNext() )
						finds.add( iter.next().mul( got ) );
				}
				// value/got=expect
				if( 0 != got )
				{
					value = got * expect;
					iter = this.find13( value, subSrc ).iterator();
					while( iter.hasNext() )
						finds.add( iter.next().div( got ) );
				}
				// got/value=expect
				if( got >= expect && expect != 0 && got % expect == 0 )
				{
					value = got / expect;
					iter = this.find13( value, subSrc ).iterator();
					while( iter.hasNext() )
						finds.add( new Expression( got ).div( iter.next() ) );
				}
			}
			return finds;
		}
	}

	private List<Expression> allPossibleProducts( int a, int b )
	{
		return this.allPossibleProducts( new Expression( a ), new Expression( b ) );
	}

	/**
	 * ������<code>a,b</code>��ɵ����п��ܵı��ʽ������+,-,*,/
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	private List<Expression> allPossibleProducts( Expression a, Expression b )
	{
		ArrayList<Expression> list = new ArrayList<Expression>( 4 );
		list.add( a.clone().add( b.clone() ) );
		list.add( a.clone().mul( b.clone() ) );
		// make sure that a <= b
		if( a.getValue() > b.getValue() )
		{
			Expression temp = a;
			a = b;
			b = temp;
		}
		list.add( b.clone().minus( a.clone() ) );
		if( 0 != a.getValue() && 0 == b.getValue() % a.getValue() )
			list.add( b.clone().div( a.clone() ) );
		return list;
	}

	private Collection<Expression> wrap( Expression ... expressions )
	{
		if( null == expressions || 0 == expressions.length )
			return Collections.emptyList();
		List<Expression> list = new ArrayList<Expression>( expressions.length );
		for( int i = 0; i < expressions.length; i++ )
			list.add( expressions[i] );
		return list;
	}

	/**
	 * @param array
	 * @param exclusiveIndex
	 * @return
	 */
	private int[] newArray( int[] array, int exclusiveIndex )
	{
		int[] a = new int[array.length - 1];
		int i = 0;
		for( int j = 0; j < array.length; j++ )
		{
			if( j == exclusiveIndex )
				continue;
			else
			{
				a[i] = array[j];
				i++;
			}
		}
		return a;
	}
}
